//https://leetcode.cn/problems/reverse-linked-list/
package codeRandomThoughts.Test206反转链表;

import codeRandomThoughts.utils.ListNode;

public class Solution {
    //还是用假头结点吧
    public ListNode removeHead(ListNode head) {
        ListNode node = head.next;
        head.next = head.next.next;
        return node;
    }

    public void addHead(ListNode head, ListNode node) {
        node.next = head.next;
        head.next = node;
    }

    /**
     * 主函数
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode fakeHead = new ListNode(0);
        ListNode res = new ListNode();
        fakeHead.next = head;
        while (fakeHead.next != null) {
            ListNode listNode = removeHead(fakeHead);
            addHead(res, listNode);
        }
        return res.next;
    }

    /**
     * 三指针法
     * prev 上一个结点
     * curr 现在的结点
     * next 下一个结点
     * 让现在结点指向上一个结点
     *
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = new ListNode();
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;//这里为什么返回这个
        //这个prev相当于是之前链表的最后一项
        //又因为这个算法相当于把链表里面的箭头倒置,所以之前的最后一项就是现在的第一项
    }

    // 从后向前递归
    ListNode reverseList3(ListNode head) {
        // 边缘条件判断
        if (head == null) return null;
        if (head.next == null) return head;

        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    }

}
